package com.wanghe.rank;

import java.util.Arrays;

/**
 * 归并排序 - 自顶向下实现
 *
 * @author He Wang
 * @date 2020/06/12
 */
public class MergeSort {

    public static void main(String[] args) {

        int[] a = {7, 9, 6, 5, 0, 4, 8, 6, 8, 5, 1};
        MergeSort mergeSort = new MergeSort();
        mergeSort.sort(a, 0, 10);
        System.out.println(Arrays.toString(a));

    }

    /**
     * 对数组进行归并排序
     * @param a     需要进行排序的数组
     * @param low   数组下标的最低值
     * @param high  数组下标的最高值
     */
    private void sort(int[] a, int low, int high) {
        if (high <= low) {
            return;
        }
        int mid = low + (high - low)/2;
        sort(a, low, mid);
        sort(a, mid+1, high);
        merge(a, low, mid, high);
    }

    /**
     * 对两个子数组(a[low...mid]和a[mid+1...high])进行归并
     *
     * @param a     需要进行排序的数组
     * @param low   数组下标的最低值
     * @param mid   数组下标的中间值
     * @param high  数组下标的最高值
     */
    private void merge(int[] a, int low, int mid, int high) {

        int[] aLow = new int[mid - low + 1];
        for (int i = 0; i < aLow.length; i++) {
            aLow[i] = a[low + i];
        }

        int[] aHigh = new int[high - mid];
        for (int i = 0; i < aHigh.length; i++) {
            aHigh[i] = a[mid + 1 + i];
        }

        // 在传入的数组a中进行本地排序
        int i = 0;
        int j = 0;
        for (int k = low; k <= high; k++) {
            if (i >= aLow.length) {
                while (j < aHigh.length) {
                    a[k++] = aHigh[j++];
                }
                break;
            }
            if (j >= aHigh.length) {
                while (i < aLow.length) {
                    a[k++] = aLow[i++];
                }
                break;
            }
            if (aLow[i] <= aHigh[j]) {
                a[k] = aLow[i++];
            } else {
                a[k] = aHigh[j++];
            }
        }

    }

}
